/**
 * 实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn ）。
 * @param x 
 * @param n 
 * @returns 
 */

function dealParams(x: number, n: number) {
    if (n < 0) {
        x = 1 / x
        n = -n
    }
}

// 解法1，直接暴力循环,超时
function myPow(x: number, n: number): number {
    if (x === 0) {
        return 0;
    }
    if (x === 1) {
        return 1;
    }
    if (n === 0) {
        return 1
    }
    if (n < 0) {
        x = 1 / x;
        n = -n;
    }
    let result: number = 1
    let times: number = 0
    while (times < n) {
        result *= x;
        times++;
    }
    return result
};

// 解法2： 分治法

/**
 * 
 * @param x 
 * @param n 
 * @returns 
 */
function myPow2(x: number, n: number): number {
    if (x === 0) {
        return 0;
    }
    if (x === 1) {
        return 1;
    }
    if (n === 0) {
        return 1
    }
    if (n < 0) {
        x = 1 / x;
        n = -n;
    }
    const divideConquer = function (x: number, n: number):number{
        // 1.terminator
        if(n===1){
            return x
        }
        if (n === 0) {
            return 1;
        }
        // 2. process (split your big problems)
        // 这里每次都取 1/2n的向下取整作为指数，作为子问题
        // 3. drill down (subproblems)
        const subresult = divideConquer(x, Math.floor(n / 2));
        // 4. merge(subresult)
        // 当前层的结果，就等于子问题的结果相乘。如 2^10 === 2^5 + 2^5
        // 如果是奇数由于上一步是向下取整的，所以需要手动乘以一个x
        return n % 2 === 1 ? subresult * subresult * x : subresult * subresult
        // 5. reverse states, 这里不用
    }
    return divideConquer(x,n);
};

// 解法3 快速幂 + 迭代
// 每个二进制数位都有一个权值，权值如下图所示，最终结果就等于所有二进制位为1的权值之积，, 
// 例如上述 x^77次方对应的二进制 (1001101) 和每个二进制位的权值如下
// 1	0	0	1	1	0	1
// x^64	x^32	x^16	x^8	x^4	x^2	x^1
// 最终结果就是所有二进制位为1的权值之积：x^1 * x^4 * x^8 * x^64 = x^77
function myPow3(x: number, n: number): number {
    if (x === 0) {
        return 0;
    }
    if (x === 1) {
        return 1;
    }
    if (n === 0) {
        return 1
    }
    if (n < 0) {
        x = 1 / x;
        n = -n;
    }
    let result:number=1; 

    // 权值初值为x, 即二进制位第1位的权值为x^1
    let weight:number = x;
    while( n<0){
        // 如果n%2为1，则表示当前二进制位为1， 让结果乘上这个二进制位上的权值, 
        // 该位权值在上一轮迭代中已经计算出来了
        // 这里对应的二进制位时从低位到高位的
        if(n % 2 === 1){
            result *= weight;
        }
        // 计算下一个二进制位的权值
        weight *= weight;
        n = Math.floor(n/2);
    }
    return result;
};